我第一想說的主題是雜湊，也就是 Hash， 因為 md5 就是一種 Hash，不了解 Hash 也無從介紹起。但由於 Hash 的概念較為抽象，即使資工系大一的資料結構中已有納入 Hash，我大學時完全不知道用途何在...。故我覺得要學 Hash 的話，先從它最常見的應用「雜湊表」 開始為佳。

雜湊表(Hash Table)這名詞可能讓人覺得十分陌生，不過如果我改稱它為

• Dictionary
• Ruby 的 Hash
• Javascript 的 Object

大家應該就明白了，就是那個用起來很像 Array 但不知為何 index 不需要是從 0 開始的整數，而可以是任意數值的資料型別。總之是一個「索引值」對應到「數值」的組合：{key: value}

h = {
  kevin: 'boy',
  gina: 'girl',
  taiwan: 'no. 1'
}
h[:taiwan]
# => 'no. 1'

不知道有沒有人好奇：那我們用 Array 做什麼？用 Hash Table 時不是也可以用數字當做 key...，反正聽說都是 O(1)。事實上兩者完全不同，C語言中，Array 是在記憶體中先設定好連續的一串空間， 而 Hash Table，抱歉，C 語言中沒有 Hash Table。

咦？所以像 Python, Ruby 等用 C 寫出來的語言怎麼會有 Hash Table 呢？實際上就是它們自行撰寫的函式庫。其實隱藏在背後的依然是一個 Array，而且這時我們幫那個 Array 取了另外的名字：桶子(Buckets)。每次一個 key 出現時，Hash Table 會經過一個處理將 key 對應到它背後的一個桶子。例如我們現有：

h = {
  a: 1,
  b: 2,
  c: 3
}

大概像這樣, 'a', 'b', 'c' 分別對應到 1, 4, 10 的 Bucket 並把數值存在其中。那個將 key 轉換成 bucket 的索引的過程，就叫雜湊 Hash。負責轉換的方程式就叫 Hash Function。我們現在暫不討論怎麼有這種神奇的方程式。先說另一個 Hash 的重點 - 碰撞。

碰撞 Collision

如果兩個不同的值放到 Hash Function 中結果產生一樣的結果，我們就稱之為碰撞。就算Hash Function 再厲害，每次都可以對應到一個其它 key 不曾對應過的 Bucket ， Bucke 總有用完的一天。假設 Buckets 已經滿了，我們現在要將 {'z' => 15} 存入 Hash Table 中，那該怎麼辦呢？

為了處理這這時我們可利用 Linked List 再將要存的值數值連到 'Z' 對應的 Bucket 中：

雜湊方程式 Hashing Function 的選擇實際上是完全自由心證，你可以自己設計自己的方程式，但實務上會依靠數學家的做法，因為這種方程式是很奇妙的。多數主流語言已經幫你選好了，直接就使用 Hash Table。我們下一篇文章會大略介紹如何制作 Hash Function。總之這邊大概知道 Hash Table 是 Hash 非常常見的應用了。